package io.openmessaging;

public class 背包问题 {


    public static void main(String[] args) {
        int[] sp=new int[]{2,3,4,5};
        int[] price=new int[]{3,4,5,6};
        int size=8;
        int dp[][]=new int[sp.length][price.length];
        for(int i=0;i<sp.length;i++){
            for(int j=0;j<size;j++){
                //当前选取的物品背包能不能装的下
                if(sp[i]<j){
                    //如果可以放入，那就要比较预留下足够空间的情况下最大的价值+当前物品的价值和不放入当前的哪个大
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-sp[i]]+price[i]);
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        System.out.println(dp);
    }
}
